package datastructures.list.singletrack;

import java.util.Collection;
import java.util.Iterator;
import java.util.Stack;

/**
 * single track linked list.
 * thread unsafe
 *
 * @author hck
 */
public class SingleTrackLinkedList<T> {
    /**
     * head of list
     */
    private Node head;
    /**
     * size of this linked list
     */
    private int size;

    /**
     * empty list
     */
    public SingleTrackLinkedList() {
    }

    public SingleTrackLinkedList(T data) {
        add(data);
    }

    public SingleTrackLinkedList(Collection<T> collection) {
        addBatch(collection);
    }


    /**
     * 反向打印链表
     * <p>
     * 思路:
     * 单链表的特性是只能单向顺序访问链表,才能将指针移动到链表尾部.
     * 但是需要我们要求我们只能从后往前访问数据.
     * 这时我就考虑,单链表的每个节点都只有next节点指针,要是能保存上一个节点的状态就好了
     * 就可以保证我们先将指针移动到最后一个节点.访问了最后一个节点再向前移动.
     * 这时我就突然想到了两个东西:
     * 一个是栈,因为很明显,栈的特性就是先入后出.
     * 第二个是递归,通过递归去遍历链表,这样也可以实现每一层递归方法栈都能hold住节点.
     * 这两个方法本质上都是依赖于栈的特性实现的
     */
    public void reversePrint() {
        System.out.println("递归打印:");
        reverseRecursivePrint(head);
        System.out.println("");
        System.out.println("利用栈打印");
        reverseStackPrint();
    }

    private void reverseStackPrint() {
        Stack<Node> stack = new Stack<>();
        Node index = head;
        while (index != null) {
            stack.push(index);
            index = index.next;
        }
        while (!stack.isEmpty()) {
            System.out.print(stack.pop().getData() + " ");
        }
    }

    /**
     * 递归打印
     *
     * @param node
     */
    private void reverseRecursivePrint(Node node) {
        if (node.next == null) {
            System.out.print(node.getData() + " ");
        } else {
            reverseRecursivePrint(node.next);
            System.out.print(node.getData() + " ");
        }
    }

    /**
     * reverse list
     * 1. 准备一个 freshHead节点
     * 2. remove当前head
     * 3. 用当前head替换freshHead节点
     * 4. 把旧的freshHead当做新的freshHead节点的next
     * ......语言描述很苍白,自己都看不懂
     */
    public void reverse() {
        if (head == null || size == 1) {
            return;
        }
        Node freshHead = null;
        while (head != null) {
            //  取下当前list的head
            Node currentHead = head;
            head = head.next;
            currentHead.next = null;
            //  交换新的节点的头和next
            Node next = freshHead;
            freshHead = currentHead;
            freshHead.next = next;
        }
        head = freshHead;
    }

    /**
     * Bulk insert element
     *
     * @param collection a group of element
     */
    private void addBatch(Collection<T> collection) {
        if (collection.isEmpty()) {
            return;
        }
        Iterator<T> iterator = collection.iterator();
        //  if head node not exist
        if (head == null) {
            head = new Node(iterator.next());
            size++;
        }
        Node index = head;
        //  move index to the last node
        while (index.next != null) {
            index = index.next;
        }
        //  add element to this list
        while (iterator.hasNext()) {
            index.next = new Node(iterator.next());
            size++;
        }
    }

    /**
     * insert linked element
     *
     * @param data element
     */
    public void add(T data) {
        if (data == null) {
            return;
        }
        size++;
        if (head == null) {
            head = new Node(data);
            return;
        }

        Node index = head;
        while (index.next != null) {
            index = index.next;
        }
        index.next = new Node(data);
    }

    /**
     * return the size of list
     *
     * @return
     */
    public int size() {
        return size;
    }

    public T get(int index) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException();
        }
        Node node = getNodeByIndex(index);
        return node.getData();
    }

    public T remove(int index) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException();
        }
        Node prefixNode = getNodeByIndex(index - 1);
        Node removeNode = prefixNode.next;
        Node nextNode = removeNode.next;

        if (nextNode == null) {
            prefixNode.next = null;
            return removeNode.getData();
        }

        prefixNode.next = nextNode;
        return removeNode.getData();
    }

    private Node getNodeByIndex(int index) {
        Node node = head;
        for (int i = 0; i < index; i++) {
            node = node.next;
        }
        return node;
    }

    public void print() {
        if (head == null) {
            System.out.println("[]");
            return;
        }
        StringBuilder stringBuilder = new StringBuilder("[");
        Node index = head;
        while (index != null) {
            stringBuilder.append(index.getData()).append(",");
            index = index.next;
        }
        stringBuilder.deleteCharAt(stringBuilder.length() - 1);
        stringBuilder.append("]");
        System.out.println(stringBuilder.toString());
    }


    /**
     * data node
     */
    private class Node {
        private T data;
        private Node next;

        Node(T data) {
            this.data = data;
        }

        T getData() {
            return data;
        }
    }
}
